#include "string_array.h"

using namespace std;

myStr::myStr(const char *str)
{
    int i;
    length=0;
    while(str[length]!='\0')
    {
        length++;
    }
    place=length+1;
    data=new char[length+2];
    
    for(i=1;i<length+2;i++)
    {
        data[i]=str[i-1];
    }
    next=new int[length+1];
    nextVal=new int[length+1];
    this->kmp_next();
    this->kmp_nextVal();
}

myStr::myStr(const int &num)
{
    length=num;
    place=length+1;
    data=new char[place+1];
    data[place]='\0';
    next=new int[length+1];
    nextVal=new int[length+1];
}

myStr::~myStr()
{
    delete [] data;
    delete [] next;
    delete [] nextVal;
}

void myStr::print()
{
    for(int i = 1; i < this->length+1; i++)
        cout << this->data[i];

    cout << endl;
}

void myStr::kmp_next()
{
    next[1]=0;
    int count=0;
    for(int i=2;i<place;i++)
    {
        next[i]=count+1;
        if(data[i]==data[1+count])
        {
            count++;
        }
        else if(data[i]==data[1])
        {
            count=1;
        }
        else
        {
            count=0;
        }
    }
}

void myStr::kmp_nextVal()
{
    nextVal[1]=0;
    for(int i=2;i<place;i++)
    {
        if(data[i]==data[next[i]])
        {
            nextVal[i]=nextVal[next[i]];
        }
        else
        {
            nextVal[i]=next[i];
        }
    }
}

void myStr::printNext(){
    for(int i = 1; i < length+1; i++)
        cout << next[i];
    cout << endl;
}

void myStr::printNextVal(){
    for(int i = 1; i < length+1; i++)
        cout << nextVal[i];
    cout << endl;
}

myMatrix::myMatrix(const int &rnum, const int &cnum, const int &nnum, const int *matrix)
{
    rowNum=rnum;
    colNum=cnum;
    nodeNum=nnum;
    nodeList=new matrixNode[nodeNum];
    for(int i=0;i<nodeNum*3;i++)
    {
        if(i%3==0)
        {
            nodeList[i/3].row=matrix[i];
        }
        else if(i%3==1)
        {
            nodeList[i/3].col=matrix[i];
        }
        else
        {
            nodeList[i/3].value=matrix[i];
        }
    }
}

myMatrix::myMatrix()
{
    colNum=0;
    rowNum=0;
    nodeNum=0;
}

myMatrix::~myMatrix()
{
    delete [] nodeList;
}
void myMatrix::swapNode(matrixNode&n1,matrixNode&n2)
{
    int temp;
    temp=n1.col;
    n1.col=n2.col;
    n2.col=temp;
    temp=n1.row;
    n1.row=n2.row;
    n2.row=temp;
    temp=n1.value;
    n1.value=n2.value;
    n2.value=temp;
}
void myMatrix::arrangeNode()
{
    for(int i=nodeNum-2;i>=0;i--)
    {
        for(int j=0;j<=i;j++)
        {
            if(nodeList[j].row>nodeList[j+1].row)
            {
                swapNode(nodeList[j],nodeList[j+1]);
            }
            else if(nodeList[j].row==nodeList[j+1].row)
            {
                if(nodeList[j].col>nodeList[j+1].col)
                {
                    swapNode(nodeList[j],nodeList[j+1]);
                }
            }
        }
    }
}

void myMatrix::printMatrix()
{
    cout << rowNum << "," << colNum << "," << nodeNum << endl;
    this->arrangeNode();
    for(int i = 0; i < nodeNum; i++)
        cout << nodeList[i].row << "," << nodeList[i].col << "," << nodeList[i].value << endl;
}
void myMatrix::FastTransposeSMatrix(myMatrix &matrix)
{
    matrix.nodeList=new matrixNode[nodeNum];
    matrix.rowNum=colNum;
    matrix.colNum=rowNum;
    matrix.nodeNum=nodeNum;
    for(int i=0;i<nodeNum;i++)
    {
        matrix.nodeList[i].row=nodeList[i].col;
        matrix.nodeList[i].col=nodeList[i].row;
        matrix.nodeList[i].value=nodeList[i].value;
    }
    matrix.arrangeNode();
}
/**/

int kmpMatch(const myStr &mstr, const myStr &tstr)
{
    int i,j,k;
    i=1;
    j=1;
    k=1;
    int flag;
    if(tstr.length>mstr.length)
    {
        return -1;
    }
    while(i+tstr.length<=mstr.place)
    {    
        flag=1;
        for(k=j;k<tstr.place;k++)
        {
            if(tstr.data[k]!=mstr.data[i+k-1])
            {
                flag=0;
                break;
            }
        }
        if(flag==1)
        {
            return i;
        }
        else
        {
            if(tstr.nextVal[k]==0)
            {
                i+=1;
                j=1;
            }
            else
            {
                i+=tstr.nextVal[k];
                j=tstr.nextVal[k];
            }
            
        }
    }
    return -1;
}

int simpleMatch(const myStr &mstr, const myStr &tstr)
{
    int i,j;
    int flag;
    for(i=1;i<mstr.place;i++)
    {
        flag=1;
        for(j=1;j<tstr.place;j++)
        {
            if(tstr.data[j]!=mstr.data[i+j-1])
            {
                flag=0;
                break;
            }
        }
        if(flag==1)
        {
            return i;
        }
    }
    return -1;
}
void substr(const myStr &mstr,const int &start,myStr &fstr,myStr &rstr)
{
    int point=start-1;
    int i;
    for(i=1;i<=point;i++)
    {
        fstr.data[i]=mstr.data[i];
    }
    for(i=start;i<=mstr.length;i++)
    {
        rstr.data[i-point]=mstr.data[i];
    }
}
/**/
bool replaceStr(myStr &mstr, const int &start, const myStr &tstr, const myStr &str)
{
    int num=mstr.length+str.length-tstr.length;
    myStr newstr(num);
    myStr* temp=&mstr;
    myStr fstr(start-1);
    myStr rstr(mstr.length-start+1);
    substr(mstr,start,fstr,rstr);
    int tag=kmpMatch(rstr,tstr)+fstr.length;
    if(kmpMatch(rstr,tstr)!=-1)
    {
        for(int i=1;i<tag;i++)
        {
            newstr.data[i]=mstr.data[i];
        }
        for(int i=tag;i<tag+str.length;i++)
        {
            newstr.data[i]=str.data[i-tag+1];
        }
        if(tag-1+str.length==num)
        {
            newstr.data[num+1]='\0';
        }
        else
        {
            for(int i=tag+tstr.length;i<mstr.place;i++)
            {
                newstr.data[i-tstr.length+str.length]=mstr.data[i];  
            }
        }
        delete [] mstr.data;
        delete [] mstr.next;
        delete [] mstr.nextVal;
        mstr.data=new char[newstr.place+1];
        mstr.next=new int[newstr.place];
        mstr.nextVal=new int[newstr.place];
        mstr.length=newstr.length;
        mstr.place=newstr.place;
        for(int i=1;i<=newstr.place;i++)
        {
            mstr.data[i]=newstr.data[i];
        }
        return true;
    }
    else
    {
        return false;
    }
}
